/*
题目:分割回文串Ⅱ
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。
https://leetcode.cn/problems/palindrome-partitioning-ii/
 */
public class MinCutⅡ {
    public int minCut(String s) {
        // 还是和上一次一样的思路, 只不过我们先储存所有所有的回文串
        int n = s.length();
        // 表示 [i, j] 是不是回文串
        boolean[][] isPalind = new boolean[n][n];

        // 初始化
        for (int i = 0; i < n; i++) {
            isPalind[i][i] = true;
        }

        // 找出所有回文串
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // 左端和右端字母相等, 并且内部也是回文串, 除非该长度为 2
                if (s.charAt(i) == s.charAt(j) && (i - j == 1 || isPalind[j + 1][i - 1])) {
                    isPalind[j][i] = true;
                }
            }
        }

        // [0, i] 的最少分割次数
        int[] dp = new int[n];
        for (int i = 0; i < n; i++)
            dp[i] = i;// 初始化

        for (int i = 1; i < n; i++) {
            if (isPalind[0][i]) {
                dp[i] = 0;
            } else {
                for (int j = i; j > 0; j--) {
                    if (isPalind[j][i]) {
                        dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                    }
                }
            }
        }

        return dp[n - 1];
    }

    // 我的动归慢如屎 ----------------------------------------------------------------------------------------------------
    public int minCutShit(String s) {
        int n = s.length();
        // 到 i 下标时的最少分割次数
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = i;
        }

        for (int i = 1; i < n; i++) {
            if (isPalindrome(s, 0, i)) {
                dp[i] = 0;
            } else {
                for (int j = i; j > 0; j--) {
                    if (isPalindrome(s, j, i)) { // [j, i] 是回文串
                        dp[i] = Math.min(dp[j - 1] + 1, dp[i]);
                    }
                }
            }
        }

        return dp[n - 1];
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}
